1. Field of the Invention
The present invention relates to a cache controller and a cache control method for controlling a cache memory.
2. Prior Art
Major computer systems today employ a memory hierarchy. In the memory hierarchy, a storage device which has a high access speed but is expensive and a storage device which has a low access speed but is less costly are used in combination, to realize a high-speed, large-capacity storage system at low cost.
In general-purpose personal computers, for example, storage devices such as registers in a microprocessor, a cache memory, a main memory, and a hard disk are organized in a hierarchy.
The cache memory has a higher access speed than the main memory. Accesses, such as reads and writes, to the cache memory are controlled by a cache controller. If data requested by the microprocessor is not found in the cache memory, the cache controller reads a set of data including the requested data stored at consecutive addresses from the main memory, and stores the set of data to the cache memory.
Such a data transfer from the main memory to the cache memory is called caching. The unit of data that can be cached is a line (or a block), which is also the unit of data that can be stored in the cache memory.
Also, a failure to find the requested data in the cache memory is called a cache miss.
When the cache miss occurs, the cache controller caches the set of data including the requested data from the main memory in units of lines. During this time, the microprocessor is placed in a wait state.
On the other hand, if the requested data is found in the cache memory, it is called a cache hit. A ratio of cache hits to all accesses to the cache memory is called a hit rate.
Access patterns of programs executed by the microprocessor have two properties: spatial locality and temporal locality. Spatial locality means if one address in the main memory is accessed then nearby addresses are also likely to be accessed soon afterward. Temporal locality means if one address in the main memory is accessed once then the same address is likely to be accessed again soon afterward. Accordingly, there is a high probability that the set of data cached in units of lines in response to the cache miss may be accessed soon.
The cached set of data is stored in a designated region of the cache memory in units of lines, according to a predetermined cache control method (mapping method).
Full associative mapping, direct mapping, and set associative mapping are three main cache control methods. These methods are described in detail in T. Saito & K. Omori Contemporary Computer Architecture Principles Ohmsha, Apr. 10, 1994, p. 112.
Full associative mapping can store data in any available location in the cache memory, and has the highest cache utilization efficiency. This method, however, needs a large number of comparators and so is not commonly used.
Suppose direct mapping or set associative mapping is used for caching in a computer system that concurrently executes tasks A and B in time-sharing. In this case, set of data A cached to execute task A may be stored into a place where set of data B cached to execute task B is stored. When this occurs, set of data B is overwritten with set of data A and erased.
Data which is to be accessed to execute task B is unlikely to be contained in set of data A. Therefore, overwriting set of data B with set of data A increases the possibility that the hit rate of task B will drop.